package com.tom.architect02.structure.hashmap;

import java.util.Map;

/**
 * Added by Tom on 2024/02/20.
 * 如果使用数组，复杂度是O(n)级别。
 * 散列列表，复杂度优化到O(1)级别。数组(散列列表 key有hashCode)，根据index在去遍历链表。最快的情况复杂度是O(1).
 */
public class HashMap<K, V> {
    // 用数组把她存起来。散列table 【桶】。
    public MapEntry[] table /*= new MapEntry[10]*/;
    transient int size; // 当前存放的数量。
    int threshold = 8; // 扩容的峰值,阈值
    final float loadFactor = 0.75f;  // 扩容因子，数组  散列到0.75就扩容。

    public class MapEntry<K, V> {
        K key;
        V value;
        MapEntry<K, V> next; // 链表中的 下一个节点
        int hash; // key的hash值

        public MapEntry(int hash, K key, V value, MapEntry<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public V put(K key, V value) {
        if (table == null) {
            table = new MapEntry[8];
        }
        if (key == null) {
            // TODO 处理key是空的情况，参考hashMap源码。
            return null;
        }
        // 1.找到tab中的位置。拿到桶的位置。hashInt。
        int hash = hash(key);
        int index = getIndex(hash, table.length); //
        // 2.判断有没有存在key了。
        for (MapEntry<K, V> e = table[index]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 找到了：(e.key ==key || key.equal(e.key))
                V oldValue = e.value;
                e.value = value; // 值覆盖
                return oldValue; // 返回原来的旧值
            }
        }
        // 3. 添加一个新的MapEntry
        addEntry(hash, key, value, index);

        return null;
    }

    /**
     * 添加一个新的Entry
     */
    private void addEntry(int hash, K key, V value, int index) {
        // hash_shift 16: value() >> 16
        // 判断是否要扩容 jni源码：mask_bits(value() >> hash_shift, hash_mask)
        // 1. hash值相等，2个对象不一定相等（2个对象不相等，hash 值有可能相等）
        // 2. hash值不相等的2个对象， 2个对象肯定不相等；
        if (size >= threshold && table[index] != null) {
            resize(size << 1); // 扩容: 带符号右移一位，扩大一倍
            // 重新计算index
            index = getIndex(hash, table.length);
        }
        // 添加
        createEntry(hash, key, value, index);
        size++;
    }

    /**
     * 创建一个新的Entry
     *
     * @param hash
     * @param key
     * @param value
     * @param index
     */
    private void createEntry(int hash, K key, V value, int index) {
        MapEntry<K, V> newEntry = new MapEntry(hash, key, value, table[index]);
        table[index] = newEntry; // 当到链表的最前面。
        size++;
    }

    /**
     * @param newCapacity 新的容量, 扩容后index会变化。
     */
    private void resize(int newCapacity) {
        // 重新开辟空间
        MapEntry<K, V>[] newTable = new MapEntry[newCapacity];
        // 扩容后index汇编，时间复杂度是O(n)
        transform(newTable);

        table = newTable;
        threshold = (int) (newCapacity * loadFactor); // 扩容因子。链表中的长度。
    }

    // 重新计算，挪动。散列。 插入链表
    private void transform(MapEntry<K, V>[] newTable) {
        int newCapacity = newTable.length; // 新数组的长度。

        for (MapEntry<K, V> e : table) { // 外层：数组遍历。
            while (null != e) { // 内层：单链表遍历
                // 从原来的数组中，获取数据Entry， 还要保证新的数据能链上。
                MapEntry<K,V> next = e.next;
                int index = getIndex(e.hash, newCapacity); // 重新计算index。

                // 保证新的能链上
                e.next = newTable[index];
                newTable[index] = e; // 搬运item
                e = next; // 新增的元素，作为链表头。不断地遍历链表。
            }
        }
    }

    // 通过hash值，找到tab 的Index
    // 为什么是2的幂次？ eg: 6 7 可能得到的index为相同的值，不够散列。
    // 更散列，降低查询的时间复杂度。让散列更散开。
    private int getIndex(int hash, int length) {
        return hash & (length - 1); // 永远不会超过table的长度。
    }

    private int hash(K key) {
        int h = 0;
        // 无符号 右移16位。 然后异或。
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    // 查找
    public V get(K key) {
        if (key == null) {
            // TODO 自己处理,参考源码
            return null;
        }
        MapEntry<K, V> entry = getEntry(key);
        return entry == null ? null : entry.value;
    }

    private MapEntry<K, V> getEntry(K key) {
        // 1.找到桶
        int hash = hash(key);
        int index = getIndex(hash, table.length);

        // 2. 遍历链表。判断有没有存在 该key
        for (MapEntry<K, V> e = table[index]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 找到了：(e.key ==key || key.equal(e.key))
                return e; // 返回原来的旧值
            }
        }
        return null;
    }

    public int getSize() {
        return table.length;
    }

}
